//
//  Permutation.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/6/12.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  面试题08.08 有重复字符串的排列组合 中等

import UIKit

/*
 有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

 示例1:

  输入：S = "qqe"
  输出：["eqq","qeq","qqe"]
 示例2:

  输入：S = "ab"
  输出：["ab", "ba"]
 提示:

 字符都是英文字母。
 字符串长度在[1, 9]之间。
 */


class Permutation: NSObject {
    
    var resultArr:Array<String> = []
    
    
    func permutation(_ S: String) -> [String] {
        
        
        var array = [String]()
        for item in S.enumerated(){
            array.append(String(item.element))
        }
        
        let sourceArr = array.sorted()
        
        let boolArr = Array.init(repeating: false, count: sourceArr.count)
        
        self.dfs(0, sourceArr, [], boolArr)
        
        return resultArr
    }
    
    
    func dfs(_ lenth:Int, _ sourceArr:[String], _ tmpArr:[String], _ flagArr:[Bool]){
        
        var arr = tmpArr
        var currentFlagArr = flagArr
        
        if lenth == sourceArr.count {
//            if resultArr.contains(arr.joined(separator: "")){
//               return
//            }else{
//                resultArr.append(arr.joined(separator: ""))
//                return
//            }
            resultArr.append(arr.joined(separator: ""))
            print("得出结果￥￥￥￥￥￥￥￥￥￥￥￥￥￥\n\n\n\n\n\n\n\n\n")
            return
        }
        
        //由于是求全排列 因此不需要startIndex，每次从头开始遍历 遇到已经遍历过的continue来遍历下一个
        for index in 0 ..< sourceArr.count {

            print("查询第\(index)个元素>>>\n")
            if flagArr[index] == true {

                print("第\(index)个元素已被标记，continue\n")
                continue
            }
            
            if index > 0 && sourceArr[index] == sourceArr[index-1] && !currentFlagArr[index-1] {

                print("第\(index)个元素和第\(index-1)个元素相等，且前一个元素的标记为false，continue\n")
                continue
            }
           
            currentFlagArr[index] = true
            

            arr.append(sourceArr[index])
            print("第\(index)个元素被push，当前结果\(arr)\n")
            self.dfs(lenth+1, sourceArr, arr, currentFlagArr)
            
            arr.removeLast()
            
            print("第\(index)个元素被pop，当前结果\(arr)\n\n")
            currentFlagArr[index] = false
        }
    }
    
    
}
